import java.util.ArrayList;
import java.util.List;

public class Solution653 {
    /*public boolean findTarget(TreeNode root, int k) {
        return helper(root, root, k);
    }

    private boolean helper(TreeNode l, TreeNode r, int k) {
        if (l == null || r == null) {
            return false;
        }
        if (helper(l.left, r, k) || helper(l, r.right, k)) {
            return true;
        }
        if (l == r) {
            return false;
        }
        int sum = l.val + r.val;
        if (sum == k) {
            return true;
        }
        if (sum < k) {
            return helper(l.right, r, k);
        } else {
            return helper(l, r.left, k);
        }
    }*/
    List<Integer> list = new ArrayList<>();

    public boolean findTarget(TreeNode root, int k) {
        inorderTraversal(root);
        int left = 0, right = list.size() - 1;
        while (left < right) {
            if (list.get(left) + list.get(right) == k) {
                return true;
            }
            if (list.get(left) + list.get(right) < k) {
                left++;
            } else {
                right--;
            }
        }
        return false;
    }

    public void inorderTraversal(TreeNode node) {
        if (node == null) {
            return;
        }
        inorderTraversal(node.left);
        list.add(node.val);
        inorderTraversal(node.right);
    }
}
